De acordo com este link (link italiano , mesmo OP) esta questão está relacionada a uma mudança recente em como o kernel linux manipula números aleatórios. Em vez de dar um número não tão aleatório, o que seria inseguro, aguarda até que o sistema gere entropia suficiente. Soluções alternativas para isso são: mover o mouse durante o processo de inicialização (que acelerará a geração de entropia) ou instalar o haveged (um gerador de entropia).
Enquanto o matteo OP já tem sua resposta no link acima, estou postando aqui para ter uma versão em inglês para outros com o mesmo problema.