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

I have set up ssh key pairs between my desktop and two servers, and from the servers to my desktop, but after reinstalling the OS on my desktop, I can't re-establish the key-pair going into my desktop by this:

mkdir ~/.ssh
chmod 700 ~/.ssh
ssh-keygen -t 
ssh-copy-id username@server

I get the following error:

(names in italics changed to protect the innocent My desktop is Ubuntu, and I can't find the answer here)

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY! Someone could be eavesdropping on you right now (man-in-the-middle attack)! It is also possible that the RSA host key has just been changed. The fingerprint for the RSA key sent by the remote host is ab:cd:ef:gh Please contact your system administrator. Add correct host key in /home/user/.ssh/known_hosts to get rid of this message. Offending key in /home/user/.ssh/known_hosts:1 RSA host key for user.server has changed and you have requested strict checking. 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).

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

Step1:$Bhargava.ssh#

ssh-keygen -R 199.95.30.220

step2:$Bhargava.ssh #

ssh-copy-id [email protected]

          Enter the the password.........

step3: Bhargava .ssh #

ssh [email protected]

Welcome to Ubuntu 14.04.3 LTS (GNU/Linux 3.13.0-68-generic x86_64) * Documentation: https://help.ubuntu.com/ Ubuntu 14.04.3 LTS server : 228839 ip : 199.95.30.220 hostname : qt.example.com System information as of Thu Mar 24 02:13:43 EDT 2016 System load: 0.67 Processes: 321 Usage of /home: 5.1% of 497.80GB Users logged in: 0 Memory usage: 53% IP address for eth0: 199.95.30.220 Swap usage: 16% IP address for docker0: 172.17.0.1 Graph this data and manage this system at: https://landscape.canonical.com/ Last login: Wed Mar 23 02:07:29 2016 from 103.200.41.50

hostname@qt:~$