Você deseja ssh-keyscan
, que é distribuído com o openssh. Na página de manual :
ssh-keyscan is a utility for gathering the public ssh host keys of a num‐
ber of hosts. It was designed to aid in building and verifying
ssh_known_hosts files.
Como parte de sua reinstalação, tenha uma máquina com uma lista de chaves atualizada executando isso e, em seguida, distribua o arquivo known_hosts atualizado para o restante das máquinas.
Ou, como outros usuários mencionaram, você pode desativar o StrictHostKeyChecking. Isso abre você para ataques man-in-the-middle, embora isso não seja uma preocupação em seu ambiente.