Create an AMI for that particular instance whose key was lost and launch a new instance using that AMI. Create a new key pair for this(download the .pem file and use PuttyGen to create a new .ppk file) and download it and now we can start a new instance and check for that key pair to work and then delete the old instance and continue with the new one. For this we have to make sure the new instance is created in the same availability zone as the original one.