[TheEskimo]

It's unlikely they stored plaintext passwords. That doesn't mean that the attacker couldn't crack the hash.

More importantly, if the hacker modified the ssh binary then they could make it retransmit passwords before hashing them. Once the attacker has such a high level of access to the system it doesn't matter if the system has otherwise sound security; that security can simply be removed or altered.

I think the announcement is made as it is because it's far safer to assume the worst than the most likely or best. Even if your keys and passwords aren't compromised it doesn't hurt to change them.