I created a new Amazon Linux AMI instance and could connect just fine via ssh. Then I assigned an elastic IP to the instance and ssh suddenly stopped working.
Debug output:
debug1: Trying private key: theduke.pem
debug1: read PEM private key done: type RSA
debug3: sign_and_send_pubkey
debug2: we sent a publickey packet, wait for reply
debug1: Authentications that can continue: publickey
debug2: we did not send a packet, disable method
debug1: No more authentication methods to try.
Permission denied (publickey).
Check associating an Elastic IP address with a running instance:
Also check login when use ssh.
I experienced this myself and found there's a very simple answer. Patience. It may take up to an hour for the machine to be accessible via ssh, even when using the correct credentials and the new IP address. See this related thread about the topic where another AWS user goes over it with Amazon support:
https://forums.aws.amazon.com/message.jspa?messageID=95268