Bem, a "solução" para isso acaba sendo relacionada ao hospedeiro. O servidor é executado por uma empresa chamada HybridCluster. Ainda não sei exatamente por quê, mas para usar a autenticação de chave pública com seus servidores, a chave pública precisa ser adicionada por meio da interface do painel de controle e não manualmente no arquivo ~/.ssh/authorized_keys
.
Eu acho que tem algo a ver com eles mudando dinamicamente o hardware, então a impressão digital do host muda, o que faz com que a chave seja rejeitada, mas eu realmente não posso dizer com certeza.
Enfim, obrigado a todos que ajudaram, e espero que isso ajude um usuário pobre do HybridCluster no futuro.