No, you absolutely do NOT need to leave and rejoin the domain.
If you're using Samba 4.x or Samba 3 (in ads mode) with a recent version of Heimdal, krb5.conf can be left empty. The Heimdal Kerberos libraries are able to autodetect KDCs using DNS records. Of course, the Linux boxes must be using an AD-integrated DNS server for this to work.
Alternatively, specifying a new server in krb5.conf would also work, regardless of which Kerberos libraries (MIT Kerberos?) you're using.