Como a outra resposta afirmou, simplesmente leva tempo porque não é gerada entropia suficiente (isto é, dados aleatórios).
Você pode agilizar o processo instalando um gerador de entropia como haveged !
Basta instalar o pacote via linha de comando:
sudo apt-get install haveged