В Debian/Ubuntu та їх похідних вміст файлу known_hosts зашифровано.
За це відповідає опція HashKnownHosts в /etc/ssh/ssh_config
Для видалення запису про конкретний хост вводимо команду:

ssh-keygen -R HOSTNAME.KIEV.UA 

Це може бути корисним наприклад в разі зміни IP адреси існуючої машини, або при зміні сервера та його dns запису.