I have no inside knowledge whatsoever as I'm not on any infrastructure teams; this is entirely me guessing from publicly available information, this is not Fedora or RH inside info. Just so you know.
But, if you read between the lines of the public disclosures so far and the steps taken by both the compromised projects and other projects with whom they have likely privately communicated details of the breaches, it seems likely that what happened was simply that the ssh keys of some people with access to the targeted projects were compromised, likely via rootkits. There then seem to have been contributing factors like people storing badly-secured private keys on shared systems belonging to the initially compromised projects, which allowed other projects to be compromised via those keys.
So ultimately, no surprise, the bug's in the wetware: it's very difficult to secure a server against an attacker who has the private key of a trusted user. To the server that attacker looks precisely like that trusted user, as the key is what's used to verify the user's identity.
To me this is the only conclusion that makes sense if you look at all the projects who are requiring users to change their ssh keys and issuing warnings about storing private keys on shared systems...
Here's a (possibly not very well thought out) idea:
Have the users create a set of strings for each hour of the day, and send it to the server. Have the user create a (one use) password on his computer, and run it through a program which fetches the string from the server and and hashes it with the user's string for the current hour, then use that hash to log in. The server sends another hash back, and the client program unhashes it with the two stored strings, then sends the unhashed string back to the server (now might be a good time for the server's string to change).
That way, the hash can change any number of times, and the user only need know the current hash. The user's strings need only be communicated with the server once (but may be changed at any time, so long as both parties know), so the only time an account may be compromised is at account creation or during modification of the secure strings. Because the only hash that is ever communicated is one that may be changed immediately after communication, anyone snooping would be unable to determine the user's secure string, and the hashed password would no longer be good anyway.
tl;dr (after account creation):
1.) create one-time password
2.) send double-hashed password to server*
3.) unhash (new) password received from server*
4.) send unhashed (new) password to server*
[*] Could happen in background
Edit: You could also have the client randomly create new secure strings and send them (hashed) to the server with the hashes, and have the server later send a (hashed) response (preferably on another hash hour) telling the client which hour those new strings will be used
(feel free to replace hashed with encrypted where you see fit)