How to establish ssh key pair when “Host key verification failed”

ssh-keygen -R hostname

This deletes the offending key from the known_hosts

The man page entry reads:

-R hostname Removes all keys belonging to hostname from a known_hosts file. This option is useful to delete hashed hosts (see the -H option above).