The patches pertaining to the Debian key rollover are only available in the security repository. I just found out the hard way, that one of my machines denied access to another one, although I had “freshly generated” private keys. Ooops … until I figured that the repository for security fixes should have been in there. Now it is and the keys have been replaced.
Checked the logs and no one got in. Luckily this server is still in the preparational stage and I am always stopping sshd when disconnecting … that should be a pretty high hurdle for any attackers 
// Oliver