ssh: заменить старый host key без чистки всего файла

После переустановки сервера удаляйте конкретный ключ, а не весь known_hosts.

ssh-keygen -R old-host.example.com
ssh -o StrictHostKeyChecking=ask old-host.example.com

Как проверить результат

Новый fingerprint нужно сверить по независимому каналу.