Host key verification failed on first ssh connection

Question

I'm trying to log with ssh on my EC2 instance with a new dual-booted ubuntu 16.04. It's the first time i'm logging in with this client, so there is nothing in .ssh/known_hosts to be deleted, as it is suggested in many other posts like this one.

When I run :

ssh -i "my_key.pem" [email protected]

I get:

The authenticity of host 'servername.amazonaws.com (serverip)' can't be established.
ECDSA key fingerprint is SHA256:***************************.
Are you sure you want to continue connecting (yes/no)? 
Host key verification failed.

Since i can log with the exac same key from putty on my windows computer,and also from a mac with the same key, this doesnt seem to be key-related.

Anyone out there to help? Thanks in advance!

EDIT: i installed putty on linux, since it was working on windows. Doesnt work either.

nmap localhost gives me port 22 open. nmap my.ip doesnt.

I tried to ssh to another address, and same results on ssh and putty :(

EDIT2: not a duplicate of BitBucket: Host key authentication failed

Problem solved: it was just me who only pressed Enter on "Are you sure you want to continue connecting (yes/no)?" and not typing yes. Thanks @Kenster

Answer 1

If you do not get any option to continue to connect and it fails permanently, then you could use the command with StrictHostKeyChecking=no option like following :

ssh -i "my_key.pem" [email protected] -o StrictHostKeyChecking=no