"It is very common that initialization of the random pool takes a longer time (up to many minutes..."

And it's my experience, too. It's one reason to install something like haveged. I had boot delays in the range of minutes, without it.