Interesting paper from Tatu Ylonen. He seem to be quick on throwing out the idea of certificates only because there is no hardened CA available today? Wouldn’t it be better to solve that problem, rather than going in circles and making up new novel ways of using keys? Call it what you want, reduced to their bare essentials, in the end you either have delegated trust through a CA or a key administration problem. Whichever path you choose, it must be backed by a robust and widely adopted implementation to be successful.
As far as OpenSSH is concerned, I believe the main problem is that there is no centralized revocation functionality. You have to distribute your revocation lists via an external mechanism and ensure that all your servers are up to date. There is no built-in mechanism like OCSP, or better yet, OCSP stapling in SSH. You could use Kerberos, but it's a royal pain to set up and OpenSSH is pretty much the defacto standard when it comes to SSH servers.
