Dans un premier lieu, il faut générer les clefs, sur le client, via la commande :

$ ssh-keygen

Par défaut il s’agit de RSA en 2048 bits.
Elles seront stockées sous ~/.ssh/

La clef privée sera nommée : id_rsa
La clef publique sera nommée : id_rsa.pub

Pour une authentification avec le certificat sans devoir saisir la passphrase, il ne faut pas en saisir lors de la génération des clefs.

Maintenant que nous avons les clefs, il faut communiquer la clef publique au serveur, via une commande dédiée :

$ ssh-copy-id -i ~/.ssh/id_rsa.pub <username>@<ipaddress>

Il faudra saisir le mot de passe pour établir une connexion ssh pour la copie de la clef.
La commande permet de copier la clef publique dans le bon repertoire : ~/.ssh
avec le nom correct : authorized_keys
ainsi que les droits d’accès en 600.

Il ne reste plus qu’à effectuer la configuration sur le serveur ssh.
Pour cela, il faut éditer le fichier de configuration du daemon ssh :

# vi /etc/ssh/sshd_config

Il faut activer l’authentification via certificat :

PubkeyAuthentication yes

désactiver l’authentification de root :

PermitRootLogin no

Permettre l’authetification de root seulement par certificat :

PermitRootLogin without-password

RSAAuthentication yes
PubkeyAuthentication yes

Désactiver l’authentification par mot de passe :

PasswordAuthentication no

Désactiver PAM authentication, ne donner les droits ssh qu’à certains utilisateurs ou groupes, ici le groupe ssh

UsePAM no
IgnoreUserKnownHosts no
AllowGroups ssh

Il suffit juste pour finaliser, de relancer le service ssh :

sudo service ssh restart

Sources :
doc-ubuntu-fr/Authentification par un système de clés publique/privée
doc.fedora-fr/SSH : Authentification par clé
Prendre un café/Installer sa clé SSH sur un serveur distant
Résoudre problème de certificat sur le client :
Chris Jean/Ubuntu SSH Fix for “Agent admitted failure to sign using the key”