I was working with a C.H.I.P and the SSH host keys were regenerating each boot after upgrading to Stretch. This caused a host key mismatch every time. It turns out /etc/rc.local was a script which checked for the presence of SSH host keys, including DSA, and if found all of them it replaced itself with /etc/rc.local.orig, which is the stock does-nothing script. If it didn’t find all of them, it would delete any existing keys and regenerate all of them.
I still don’t understand why this produced the behavior it did, because the script did succeed in producing DSA keys, but replacing the weird /etc/rc.local with the /etc/rc.local.orig that just exit 0s seems to have solved the problem.