常田です。

クラウドになってサーバを作ったり消したりしていると同じIPアドレスでサーバが用意される事があります。
SSHで接続する際には接続先毎にローカルに情報が保管されるため、中身が別のサーバになったりしていると騙されてない?って怒られることになります。

$ ssh root@123.123.123.123
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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
9a:33:31:63:13:85:d3:32:c1:bb:d9:0f:cc:d9:c5:f6.
Please contact your system administrator.
Add correct host key in /Users/hideaki/.ssh/known_hosts to get rid of this message.
Offending RSA key in /Users/hideaki/.ssh/known_hosts:51
Password authentication is disabled to avoid man-in-the-middle attacks.
Keyboard-interactive authentication is disabled to avoid man-in-the-middle attacks.
Permission denied (publickey,password,keyboard-interactive).

上記のようなエラーが出た場合には ssh-keygen コマンドで情報を消してから再度実行しましょう。
(known_hostsファイルを削除する方法もありまうがこちらのほうが素直だと思います)

$ ssh-keygen -R 123.123.123.123
Host 123.123.123.123 found: line 51 type RSA
/Users/hideaki/.ssh/known_hosts updated.
Original contents retained as /Users/hideaki/.ssh/known_hosts.old

この後再度実行すると以下のように繋がります。

$ ssh@123.123.123.123
Warning: Permanently added '123.123.123.123' (ECDSA) to the list of known hosts.
Password:
Welcome to Ubuntu 14.04.2 LTS (GNU/Linux 3.13.0-48-generic x86_64)

 * Documentation:  https://help.ubuntu.com/
Last login: Tue Jul 28 01:51:25 2015 from s804105.xgsspn.imtp.tachikawa.spmode.ne.jp

以上