Сегодня для экспериментов переустановил тестовый сервер, начал к нему подключаться, а он мне и говорит:

$ ssh root@172.16.7.39
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ 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 the RSA host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
a8:1c:d3:d2:68:06:b8:74:46:ce:67:8a:f0:5e:04:44.
Please contact your system administrator.
Add correct host key in /home/beliashou/.ssh/known_hosts to get rid of this message.
Offending key in /home/beliashou/.ssh/known_hosts:1
RSA host key for 172.16.7.39 has changed and you have requested strict checking.
Host key verification failed.

Я человек нервный, иду на http://linux007.livejournal.com/tag/ssh, а там ничего на эту тему нет. Ну я как-то понял, что я ничего не понял. И заодно понял, что хочу понимать в этом больше. Поэтому я сразу нашел вот такой трактат, в котором рассказывается как эти самые ключи генерить и куда их складывать. И сразу вспомнил, что раньше я через это уже проходил, но тогда я просто прибивал файл known_hosts и информация о хостах собиралась снова (вопросиком про yes/no) про то, чтобы запомнить фингерпринт сервера.
А вот моя беда нашла решение в статье, которая специально под это заточена:

Optionally you can specify -H to have the key displayed in the hashed form. -v increases verbosity.To search for an entry in known_hosts issue:

$ ssh-keygen -H -F hostname

You can also delete a single entry from known_hosts:

$ ssh-keygen -R hostname

Собственно, именно так я научился с этим справляться. Сейчас для полного счастья ещё пойжу публичные ключи своей рабочей машинки раскидаю по серверам.