Devo esclarecer que não é sobre o SSH! Então, por favor, não marque como duplicado, provavelmente não é!
É o login simples no Ubuntu que leva uma eternidade, seja após o boot ou em uma tela de bloqueio ou sudo-promt no terminal, leva alguns minutos para processar a senha que eu digito. Tenho notado isso nos últimos dias e não me lembro de fazer grandes mudanças como atualização ou qualquer coisa. A única coisa que me lembro é de mudar o /etc/krb5.conf há alguns dias.
Muito obrigado.
Editar: