My company is serious about security and willing to move to SSH key-pairs. Users can generate their SSH key pairs independently and I worry if they set a pass-phrase. Can I enforce this? Does signing with ssh-keygen help?
No. You can't enforce on the server side that the key has passphrase. Key is always on the client side and the server sees only the signature of challenge and public key. Certificates (aka signed keys) will not help either, because the public keys are signed.
I propose you to have a look at some kind of two factor authentication or smart cards if you want to go this way in security.