Meu erro foi usar " em vez de ' . Tanto quanto eu entendo usando " faz com que o shell para interpretar a seqüência de caracteres ao executar o comando ssh na máquina local. Não tenho certeza do que estava sendo passado para as máquinas remotas, possível o resultado do comando. ' fará com que o shell passe a string inalterada.
ssh -n -o StrictHostKeyChecking=no -i ... user@host 'sudo rngd -r /dev/urandom -o /dev/random -t 10'
funciona. No final, decidi usar o haveged:
ssh -n -o StrictHostKeyChecking=no -i ... user@host 'sudo apt-get install haveged'
É tudo o que precisa ser feito. Ele instalará o haveged, o iniciará e adicionará uma entrada para que ele inicie na inicialização.