> openssh has support for full-blown certificates

Well, yes and no. Do you mean the new cert stuff that's in standard openssh? Which has stuff like:

    The marker is optional, but if it is present then it must be one of “@cert-authority”, to indicate that the
     line contains a certification authority (CA) key, or “@revoked”, to indicate that the key contained on the line
     is revoked and must not ever be accepted.  Only one marker should be used on a key line.

While certainly simple, it doesn't strike me as very manageable.

Or did you mean the x509 patch?

http://roumenpetrov.info/openssh/