Warnings: This procedure can do following things:

• In this procedure, you will stop and start the instance. So, your instance public will change. It would be better if your EC2 instance has Elastic IP.
• The EC2 instance will stop so the data in instance store volume will be lost.

Below is the best way to connect your EC2 instance if your private key (.pem file) got lost.

Step 1. Create a new key pair in AWS console.

Step 2. Retrieve the public key from the private key downloaded in step 1.

$ ssh-keygen -y -f /path_to_key_pair/key-pair.pem

Step 3. In AWS EC2 console, stop your instance.

Step 4. Goto to Actions, instance settings, and then select Edit user data

Step 5. Copy the below script into the user data dialog box:

 Content-Type: text/cloud-config; charset="us-ascii"
 MIME-Version: 1.0
 Content-Transfer-Encoding: 7bit
 Content-Disposition: attachment; filename="cloud-config.txt"
  
 #cloud-config
 cloud_final_modules:
 - [users-groups, once]
 users:
   - name: username
     ssh-authorized-keys: 
     - PublicKeypair

Replace username with an instance user names like ubuntu and ec2-user. You can determine the username of the instance by checking the username related to the AMI used (like ubuntu instance has ubuntu user and Amazon Linux has ec2-user). You get the list of user names here.

Replace PublicKeypair with the complete public key generated in step 2. Paste the complete entire public key.

Step 6. Save the changes.

Step 7. Start the EC2 Instance and let the cloud-init phase complete. Then you are able to login into the instance with the new private key.

Note: The User data still has the public key. So, it must be deleted.

Step 8. Again, open the Edit user data and delete the whole script from dialog box and save.

Step 9. Start the instance and then use the new key for login.