Na verdade, aumentar o nível de log não mostra nada relacionado.
Parece apenas que o cliente pulou a próxima chave possível (DSA) que eu não consegui e o método foi removido e a senha foi solicitada.
Meu cliente é um 14.04LTS, o servidor é 16.04LTS.
A chave foi gerada há muito tempo (quando eu estava instalado 14.04LTS).
A solução foi regenerar as chaves RSA no cliente e agora funciona como pretendido. De alguma forma, o 16.04LTS não é compatível com as chaves geradas há muito tempo.