Since creating an OpenPGP key requires some randomness (eg. move mouse, reading or writing from/to File System), the process of creating it on a remote connected host (via ssh) may take a lot of time or even get stuck.

To collect the needed entropy you can connect to the server from another SSH connection and perform some I/O task like in the following examples:

ls -R /

(recursive listing of all files in the File System)

find /var/ /usr /lib /srv -type f -print0 | xargs -0 md5sum > /dev/null

This really saved my day! :)