Eu mesmo resolvi o problema quando encontrei uma linha em dmesg
, que diz
Warning: nss-myhostname is not installed
Eu instalei nss-myhostname
e consertei meu problema. Talvez isso tenha resolvido o problema porque estou sempre usando sessões ssh e o problema costumava acontecer quando eu estava em uma conexão ativa.