How to establish ssh key pair when "Host key verification failed"

Most likely, the remote host ip or ip_alias is not in the ~/.ssh/known_hosts file. You can use the following command to add the host name to known_hosts file.

$ssh-keyscan -H -t rsa ip_or_ipalias >> ~/.ssh/known_hosts

Also, I have generated the following script to check if the particular ip or ipalias is in the know_hosts file.

#!/bin/bash
#Jason Xiong: Dec 2013   
# The ip or ipalias stored in known_hosts file is hashed and   
# is not human readable.This script check if the supplied ip    
# or ipalias exists in ~/.ssh/known_hosts file

if [[ $# != 2 ]]; then
   echo "Usage: ./search_known_hosts -i ip_or_ipalias"
   exit;
fi
ip_or_alias=$2;
known_host_file=/home/user/.ssh/known_hosts
entry=1;

cat $known_host_file | while read -r line;do
  if [[ -z "$line" ]]; then
    continue;
  fi   
  hash_type=$(echo $line | sed -e 's/|/ /g'| awk '{print $1}'); 
  key=$(echo $line | sed -e 's/|/ /g'| awk '{print $2}');
  stored_value=$(echo $line | sed -e 's/|/ /g'| awk '{print $3}'); 
  hex_key=$(echo $key | base64 -d | xxd -p); 
  if  [[ $hash_type = 1 ]]; then      
     gen_value=$(echo -n $ip_or_alias | openssl sha1 -mac HMAC \
         -macopt hexkey:$hex_key | cut -c 10-49 | xxd -r -p | base64);     
     if [[ $gen_value = $stored_value ]]; then
       echo $gen_value;
       echo "Found match in known_hosts file : entry#"$entry" !!!!"
     fi
  else
     echo "unknown hash_type"
  fi
  entry=$((entry + 1));
done

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).