Solution for RSA Host Key verification failed

When making an SSH connection to a machine we've never contacted before, The server presented its host key to the client as part of the initial handshake.
On Client when you said 'yes', SSH client saves the server's host key locally in the file $HOME/.ssh/known_hosts. for root user location is /root/.ssh/known_hosts.This file is, effectively, your personal Certificate Authority -- it is the list of all SSH server

The next time you connect to this machine, your SSH client will go through the standard steps of verifying the remote machine and allowing you to log in, this time, it did not ask you to verify the key fingerprint at all. That's because the key was in your $HOME/.ssh/known_hosts file. The SSH client actually checks in a few places:
The global known hosts file, typically /etc/ssh/ssh_known_hosts. This can be modified by changing the GlobalKnownHostsFile parameter in the ssh configuration file (typically /etc/ssh/ssh_config).
The user's known hosts file, typically $HOME/.ssh/known_hosts. This can be modified by changing the UserKnownHostsFile parameter in the ssh configuration file.

If the operating system of the host computer changes (e.g. re-install with the same hostname), an error message will occur notifying the user that the remote host ID has changed and access will be denied:

This was actually pretty easy to fix. Since you are already trying to SSH, this assumes you already know where Terminal is and you have it opened
If you are sure that the changes made to the host computer were legitimate, you can edit the known_hosts file and delete the original key. At the next login you will be prompted to verify the host machine again. This will add the correct key to the known_hosts file and allow access.

To delete the key use either of the following:

Using the GUI:

1. Browse to the home directory of the user that requires login access.
2. Browse to the ./ssh directory, and open the file named known_hosts.
   Tip: Show hidden directories, if required.
3. Find the offending key, delete, save and exit.
   Tip: If you are unsure of the correct key, simply delete them all and save the empty file. You will then be prompted again to verify any machine that had previously been given access.

Via the terminal:

1. Open a terminal session and type:
   $ vi /home/user/.ssh/known_hosts
   or
   
   $ gedit /home/user/.ssh/known_hosts
   Note: Edit the above path by amending user with the user that requires login access. For Root user path is /root/.ssh/known_hosts
   Enter the above commands as root if privileges are required to edit.
2. Find the offending key, delete, save and exit. The error actually shows you location in the Known_hosts file. The above snapshot shows that error key is on 10th line of known_hosts file (/root/.ssh/known_hosts:10)
   Tip: If you are unsure of the correct key, simply delete them all and save the empty file. You will then be prompted again to verify any machine that had previously been given access.