Duas ideias:
Primeiro, tente importar a chave para o ssh-agent com ssh-add $keyfile
para ter certeza de que é realmente um problema com o arquivo-chave e não sobre o servidor.
Em segundo lugar, busque uma cópia de sua chave privada do seu backup e use algo como cmp
para verificar se o arquivo realmente mudou.