Por algum motivo, preciso instalar o gnupg-curl
para obter suporte SSL sobre o HKP:
This package contains the keyserver helper tools built with libcurl, which replace the ones in the gnupg package built with the "curl shim" variant of gnupg. This package provides support for HKPS keyservers.
A instalação resolveu o problema.