Comment # 33 on bug 1096072 from Antonio Larrosa

I enabled fips again and rebooted to be sure the problem was reproduced again.
Then I installed the haveged package from your home, ran mkinitrd and rebooted. 
With your package, I can confirm the boot delay doesn't happen anymore.

Btw, the problem with sudo (bsc#1096050) still continues happening as I guess
that's related to fips being enabled and not the the entropy pool being empty.