The first thing I will say is ouch. The typical reasons for a finger print change are the ssh server key was re-generated (by someone), the sshd reinstalled (not just updated from yum or apt-get), your local ssh client reinstalled or --- the real reason for the check --- there is a man-in-the-middle.
In the key update scenarios, either you did it or someone else did it. If it wasn't you, then you are likely compromised.
In the MITM scenario, everything you typed was captured and is now replayable by an adversary. In which case you are likely compromised. Nothing is hidden from the MITM.
So, before you assume you are compromised, please check to make sure Dig O does not manage your service for you and does not make these changes on your behalf. Also, if you updated your local ssh client then they key could have been stomped on. Look for logical reasons not to expect the worst --- but you are very very correct to be paranoid. [personally I always expect the worst. I have worked many many dozens of very significant intrusions.]
In the worst case you merely have to scratch the OS and restore your data (not executable files, libraries, passwords or ssh_keys from a potentially corrupt backup, but just your data. If you restore services you have a race condition ... update the authentication passwords instantly.
All this assumes that any intrusion doesn't start with your local client and have propogated to the remote server -- :).
In general you should understand where that message came from and if it wasn't you -- time to get to work.