There are still real issues with managing root keys etc -- but with cert support in openssh (client and server) that provides a sane basis for trust management.
For Userify, the service (as opposed to keys, auth, servers and users: the problem) -- I think spending some time on a UI to manage certs/ca for ssh, documenting how to use it for user-keys/certs -- and offering to run a CA per Userify-account (ie: generate/manage the root CA-cert, allowing "instant security" by deploying the Userify-user's CA root cert on servers, and having a service to sign public-keys with that key) could be one very sensible approach.
There might be some added benefit with an "always on"-service, by issuing short-lived user certs (valid for, say 8 hours a la kerberos tickets) -- but for that to be useful, perhaps some work would be needed with forking putty for windows users and/or patching ssh-agent/ssh for nix/OS X users. The basic functionality is there, but the UI/UX is lacking. Note that a user can keep the secret key* for as long as he/she is comfortable -- it's only the signed public cert that needs to be updated (as the previous one expires).
Not sure if that answers your question, but those are some of my thoughts on the matter :-)
[1] http://www.openbsd.org/cgi-bin/man.cgi/OpenBSD-current/man1/...
btw, please feel free to become a user ;)
So if a service provides users with "session-tickets" (eg: certs valid for 8 hours, or 5 days etc) -- the servers need not call-back to userify. Authorization (for at least part of use-cases) becomes decentralized. Add an api for extending the validity of a cert (client does a lookup, userify checks policies, and if everything is ok, signs the key for a new validity-period) -- and everything should work very nicely indeed.
For those interested in ssh certs in general, see also:
https://github.com/cloudtools/ssh-ca
As for the userify shim, even though you've answered my question: https://github.com/userify/shim/issues/4 -- you might still want to include a license file, or something along the lines of: http://www.tarsnap.com/legal.html in the readme.
Might also want to have a free/open licensed spec of the api somewhere, so that if someone were to implement a self-hosting, free/open service that could be made api-compatible with userify, there'd be a clear way to do that legally.