Eu tive o mesmo problema com as VMs do Arch e também achei que poderia esperar por 5 minutos ou fazer login via virt-manager.
O problema é com o gerador de números aleatórios retardando a inicialização:
# journalctl --since 13:23 | grep crng
Oct 06 13:23:04 apsis kernel: random: get_random_bytes called from start_kernel+0x95/0x535 with crng_init=0
Oct 06 13:28:03 apsis kernel: random: crng init done
Veja link para detalhes.
Eu segui a sugestão de instalar o Haveged e agora posso fazer o login imediatamente após a reinicialização. O init crng agora leva apenas um segundo em vez de 5 minutos.
Espero que isso ajude.