[tashian]

SSH CAs would make the challenge a lot easier. It sounds like they are using RSA keys here for the widest possible compatibility, and while OpenSSH's certificate support is not at all new, it still may be too new for this application.

[lxgr]

Using SSH certificates would tie every Github user to OpenSSH extensions though. I'm not sure if many git clients use something else, but it's at least worth a consideration.