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! :)