If you have DNSSEC setup (and are validating using it!) you might consider using SSHFP to avoid the "The authenticity of host 'blah blah blah' can't be established." This is an alternative solution to signing the SSH host public key with a certificate.
Personally, I'd recommend the ssh ca approach as being more sensible, and foolproof, but there are situations where it's not appropriate.
run sudo ssh-keygen -r $(hostname) >>/etc/bind/db.$(hostname --domain),
resign the zone, kill -HUP $(pidof named) and you're done.