Для тех, кто замучился ждать.
Проблема с нехваткой энтропии особенно сильно напрягает при использовании виртуальных машин (на железе с энтропией обычно по-лучше), а также при использовании команд ALD в скриптах.
Скачать и установить два пакета:
libhavege1_1.9.1-1_amd64_signed.deb
haveged_1.9.1-1_amd64_signed.deb