Looks like this (same test): https://dev.gnupg.org/T5444 Workaround for the test in Debian: Set key type to RSA. Upstream dev comment: You should anyway use --quick-gen-key.