There could be various reasons for why your authentication is failing.
First of all, make sure that you are using the correct key pair. I know it sounds trivial but it could actually be an issue in cases like these.
Check if the username that you are using is correct or not. For ubuntu based AWS AMIs, the valid username is ubuntu, on others, it's ec2-user.
Check if you are connecting to the right host.