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 .