Colocando isso aqui para evitar algumas dores de cabeça futuras para pessoas que pesquisam o assunto. Eu tive dificuldade em encontrar uma boa solução. Eu não sabia que havia um arquivo de log para coisas relacionadas ao ssh.
Examinar o arquivo de log no servidor ( /var/log/auth.log ) revelou que as permissões para várias chaves em /etc/ssh/ foram definidas como 755, o que é muito aberto. Somente o usuário deve ter perms para ver estes. Então, usar chmod 400 em todas as chaves afetadas resolveu meu problema.