SSH connection problem with "Host key verification failed..." error

"Host key verification failed" means that the host key of the remote host was changed.

SSH stores the host keys of the remote hosts in ~/.ssh/known_hosts. You can either edit that text file manually and remove the old key (you can see the line number in the error message), or use

ssh-keygen -R hostname

From man page:

-R hostname
Removes all keys belonging to hostname from a known_hosts file. This option is useful to delete hashed hosts .

(which I learned from the answer to Is it possible to remove a particular host key from SSH's known_hosts file?).

If you are running in certain remote/scripting situations where you lack interactive access to the prompt-to-add-hostkey, work around it like this:

$ ssh -o StrictHostKeyChecking=no [email protected] uptime

Warning: Permanently added 'something.example.com,10.11.12.13' (RSA) to the list of known hosts.

Also sometimes there is situation when you are working on serial console, then checking above command in verbose mode -v will show you /dev/tty does not exist, while it does.

ssh -v user@hostname

In above case just remove /dev/tty and create a symlink of /dev/ttyS0 to /dev/tty.

rm /dev/tty
ln -s /dev/ttyS0 /dev/tty

As an alternative, add id_rsa.pub to the remote location, so password is not prompted and you get login access.