Your SSH client is exactly telling you why it is refusing to establich a session, and what to do:
" Add correct host key in /root/.ssh/known_hosts to get rid of this message.
Offending key in /root/.ssh/known_hosts:2
RSA host key for hostname has changed and you have requested strict checking."
Most likely on your ssh client someone has enforced strict hostkey checking, because the default setting would be "ask".
This means that your ssh client isn't, after having shown you the above warning about a discovered mismatch between advertised hostkey on the ssh server and the current entry in the user's known_hosts file of the client, as it normally would, viz. asking you to either confirm (i.e. accepting the possibly spoofed identity of the ssh server), and then letting it save the new server's ssh host key on *your* behalf, or simply aborting by disapproving.
Because you most likely have an entry like
"StrictHostKeyChecking yes" your ssh client will *never* modify your client's user's known_host file, but instead the user to manually add new or remove outdated keys.
Please, check your ssh client's global config.
e.g.
# grep -i stricthostkeycheck /opt/ssh/etc/ssh_config
# StrictHostKeyChecking ask
or if prevelant, your user's overriding config
e.g.
$ grep -i stricthostkeycheck $HOME/.ssh/config
If you wish to stick with StrictHostKeyChecking you need to manually delete the outdated host key, and add the new one.
As you are obviously using an OpenSSH release >= 4 your hostkeys, as well as names they belong to are hashed, which makes them difficult to identify by humans.
But ssh-keygen supports new options to ease the task.
You can use -F option of ssh-keygen to identify the key belonging to a particular host.
e.g.
$ ssh-keygen -F somehost
should print that hosts hashed key.
Similarily,
$ ssh-keygen -R somehost
would remove the entry for somehost.
After that you could append the new host key by e.g.
$ ssh -o stricthostkeychecking=no someone@somehost >> ~/.ssh/known_hosts
someone@somehost password: ^C
Note, you don't need to do a full login here
as the key's already been saved to someone's known_hosts (thus the ^C), which you can immediately verify.
$ ssh-keygen -F somehost
Note also, you should (even temporarily) disable strict host key checking only after you have verified that the advertised host key's fingerprint is *really* the correct one.
If this is all too much fuss,
you could relapse to "ask" by either commenting out the stricthostkeychecking directive in ssh_config (or your personel config), or setting it explicitly to ask.
Besides, you should never simply delete or clobber by redirection any user's know_hosts file.
Madness, thy name is system administration
