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.