This error has been flooding my tor log probably since April, but I only picked it up now after reading about how few relays there are listed in the directory prompted me to check that mine was working.
The standard fix for this is prevalent already: you need to delete your old keys (because they were created with a vulnerable version of OpenSSL). However, I fell into an elementary trap by doing this:
$ sudo rm -f /var/lib/tor/keys/secret*
That reported no errors… because the -f causes rm to “ignore nonexistent files and arguments”, and since stuff under /var/lib/tor/keys/ is private property of debian-tor, Bash has cannot expand secret* to what is actually there.
I thought my old keys were now gone, but when I restarted tor it kept nagging about the fingerprint. Kept me confused for a while.
So you have to have an actual root prompt for deleting those old keys with a wildcard:
$ sudo -i
# service tor stop
* Stopping tor daemon...
* ... [ OK ]
# rm -f /var/lib/tor/keys/*
# service tor start