さくらVPSでマシンを再インストールしたら、以下のエラーメッセージが出力されてMacからssh接続がつながらなくなったって話。
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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 a host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx.
Please contact your system administrator.
Add correct host key in /Users/username/.ssh/known_hosts to get rid of this message.
Offending RSA key in /Users/username/.ssh/known_hosts:1
RSA host key for xxx.xxx.xxx.xxx has changed and you have requested strict checking.
Host key verification failed.

対処方法:ホストの鍵情報を削除する。
$ rm ~/.ssh/known_hosts

理由は、クライアントに保存されているRSA鍵がサーバが異っているため。