Permission denied (publickey) when SSH Access to Amazon EC2 instance

In this case the problem arises from lost Key Pair. About this:

• There's no way to change Key Pair on an instance. You have to create a new instance that uses a new Key Pair.
• You can work around the problem if your instance is used by an application on Elastic Beanstalk.

You can follow these steps:

1. Access to AWS Management Console
2. Open Elastic Beanstalk Tab
3. Select your application from All Applications Tab
4. From left side menù select Configuration
5. Click on the Instances Gear
6. In Server Form check the EC2 Key Pair input and select your new Key Pair. You may have to refresh the list in order to see a new Key Pair you're just created.
7. Save
8. Elastic Beanstalk will create for you new instances associated with the new key pair.

---

In general, remember you have to allow your EC2 instance to accept inbound SSH traffic.

To do this, you have to create a specific rule for the Security Group of your EC2 instance. You can follow these steps.

1. Access to AWS Management Console
2. Open EC2 Tab
3. From Instances list select the instance you are interested in
4. In the Description Tab chek the name of the Security Group your instance is using.
5. Again in Description Tab click on View rules and check if your Security Group has a rule for inbound ssh traffic on port 22
6. If not, in Network & Security menù select Security Group
7. Select the Security Group used by your instance and the click Inbound Tab
8. On the left of Inbound Tab you can compose a rule for SSH inbound traffic:
   • Create a new rule: SSH
   • Source: IP address or subnetwork from which you want access to instance
   • Note: If you want grant unlimited access to your instance you can specify 0.0.0.0/0, although Amazon not recommend this practice
9. Click Add Rule and then Apply Your Changes
10. Check if you're now able to connect to your instance via SSH.

Hope this can help someone as helped me.

This error message means you failed to authenticate.

These are common reasons that can cause that:

1. Trying to connect with the wrong key. Are you sure this instance is using this keypair?
2. Trying to connect with the wrong username. ubuntu is the username for the ubuntu based AWS distribution, but on some others it's ec2-user (or admin on some Debians, according to Bogdan Kulbida's answer)(can also be root, fedora, see below)
3. Trying to connect the wrong host. Is that the right host you are trying to log in to?

Note that 1. will also happen if you have messed up the /home/<username>/.ssh/authorized_keys file on your EC2 instance.

About 2., the information about which username you should use is often lacking from the AMI Image description. But you can find some in AWS EC2 documentation, bullet point 4. : http://docs.aws.amazon.com/AWSEC2/latest/UserGuide/AccessingInstancesLinux.html

Use the ssh command to connect to the instance. You'll specify the private key (.pem) file and user_name@public_dns_name. For Amazon Linux, the user name is ec2-user. For RHEL5, the user name is either root or ec2-user. For Ubuntu, the user name is ubuntu. For Fedora, the user name is either fedora or ec2-user. For SUSE Linux, the user name is root. Otherwise, if ec2-user and root don't work, check with your AMI provider.

Finally, be aware that there are many other reasons why authentication would fail. SSH is usually pretty explicit about what went wrong if you care to add the -v option to your SSH command and read the output, as explained in many other answers to this question.

This is how I solved the problem

ssh -i <key> ec2-user@<ec2 ip>