If you use DreamHost’s VPS service you may have recently had your host server upgraded to Debian OS v6.0.2. Or maybe you’re dealing with Proactive Security Maintenance (New Login Keys)
This happened mostly through the month of August 2011 and recently in October 2012.
One of the side effects of this was that the RSA host key changed for the server. Most folks won’t notice this but if you’ve used SSH to access the server you’re probably getting the warning message below. (I changed RSA key, username and domain name to generic names in the example below.)