VirtualBox上でゲストOSを作りなおしたとき、同じIPで設定するとSSHのログイン時に警告が表示されてログインできません。
これは、以前に接続した時に保存したkeyと一致しないためです。
解決方法は保存したkeyの情報を削除します。
~/.ssh/known_hosts ファイルを開いて該当する項目を削除してください。

vi ~/.ssh/known_hosts

無事にログインできるようになりました。