Si queremos generar claves gpg a través de SSH casi seguro que no podremos porque no generamos la suficiente entropía. Existe un paquete para Debian llamado rng-tools que nos soluciona este problema.
Lo instalamos (aptitude install rng-tools) y añadimos la siguiente línea al archivo /etc/default/rng-tools:
HRNGDEVICE=/dev/urandom
Sólo falta reiniciar el servicio: /etc/init.d/rng-tools restart