Hi together, for me, after an upgrade I have exactly the same error. However, running nsd-control-setup (after moving the keys away) resolved it for me.
@Markus: I assume that an upgrade from oldstable isn't enough,I guess my current system started -3 releases or so. So as an suggestion, check in the postinst-file the size of the keys, and if it is below 2048 bits, move them away and regenerate. My personal opinionis that this change alone should be fit for a .-release, but of course please check with the release team first. Regards, Andi