Mass-updating cached hosts keys afrer ssh security upgrade?

[JW <jw@mailsw.com>]

Hello,

In the past several weeks I have applied the openssh/openssl updates to my 
systems - the updates the fix the random-number-generator weakness.

This has turned into an unexpected nightmare: my users have, between them all, 
dozens of cached host keys, and they are nearly unable to work because every 
time they turn around they're getting bad-old-cached-key warnings (REMOTE 
HOST IDENTIFICATION HAS CHANGED).

I've been trying to go through all the known_hosts files manually and update 
them to give my users a break, but it's a tedious nightmare. Adding to the 
complexity is that many of the known_hosts files are armored (the hostname/ip 
address is not in plain text).

Has anyone come up with a way to read all the cached hosts - all the 
~/.ssh/known_hosts entries on a system (or at least per user) and fix them?

Essentially I need some semi-automated way to fix this since I have many 
users's connections to fix still (hundreds if not thousands by the time I do 
machines X users X outgoing connections).

Thanks,

	JW