OpenSSH 5.4 was released on 2010-03-08, and that is when the project added support for certificate authentication of users and hosts using an OpenSSH certificate format (not X.509)
Why am I telling you this? Because I wanted to find out since when exactly I have been putting off actually experimenting with SSH certificates, and I can now with certainty say that as far as this topic is concerned I've been an idiot over the last 16 years!