Enforce SSH Private Key Passphrase Complexity

How can I enforce a passphrase policy on the passphrases that are utilized to encrypt SSH private key? I enjoyed utlizing the PAM pam_pwquality module to enforce user account password complexity, but I don't think I can utilize it with SSH key passphrases.

How can I enforce a passphrase policy on the passphrases that are utilized to encrypt SSH private key?

Generally speaking, you cannot. Private key encryption is a client-side matter, and most of the commonly-used SSH clients have no such feature (i.e. nothing like Group Policy integration), especially as it's really easy to get around such restrictions by using a different SSH client to re-encrypt the key.

A better approach might be to store the private keys in hardware (e.g. a TPM2 chip or its Apple equivalent, or a Yubikey in PIV/CCID mode) so that there would be no file that could be stolen or otherwise copied. Such hardware tokens can enforce limits on PIN attempts, and therefore can safely use a weaker PIN (i.e. not making your staff's life a pain in the ass).

For Linux, take a look at ssh-tpm-agent or tpm2_pkcs11. (If all your machines consistently have TPM2, then the special ssh-agent is easier to work with. On the other hand, if you have a mix of TPM2 and Yubikey or other smartcards, you'll be dealing with PKCS#11 a lot.) For Windows, unfortunately its own OpenSSH doesn't integrate with CryptoAPI at all, but PuTTY-CAC should work well with the "Platform Key Storage Provider", and it may be possible to connect OpenSSH to Pageant-CAC in place of ssh-agent.

Alternatively, use one of those "SSH Certificate Authority" systems which issue very short-term keypairs based on some other kind of authentication – employees log in in the morning and receive a SSH certificate usable only for that day (i.e. similar to how Kerberos works). This is not exactly X.509 certificates as in TLS, but conceptually similar – you create a CA and issue certificates to users using ssh-keygen.

I believe latest version of PuTTY supports SSH certificates, so this method is no longer limited to OpenSSH only. Various companies have written such systems internally and published them on GitHub, often specific to their own workflows; the step-CA software might work for setting this up.

Finally, if you're doing this in an Active Directory network, you might as well use the actual Kerberos that AD already has, instead of public keys. The feature is called "GSSAPI authentication" in SSH; it requires each server to have a machine account and a keytab. This way the only password or passphrase would be the same AD password that is already subject to password complexity. (It can also be set up without AD.)