Eu acho que você poderia tentar fazer
ssh -o "StrictHostKeyChecking no" -o "UserKnownHostsFile /dev/null" user@server
poderia funcionar, pois não tentaria verificar se há uma chave de servidor ... (eu não tentei isso sozinho)
(inspirado em link )