On each server, configure NIS+ authentication so that it accepts both the old and new credentials. This will require running nisauthconf(1m) and keylogin and restarting keyserv(1m). The keylogin command stores the keys for each mechanism in the /etc/.rootkey. See Keylogin With NIS+ for basic keylogin details.
In this example, the current authentication mechanism is des and the new mechanism is dh640-0. Note the ordering is significant here; any mechanisms after the des entry will be ignored for client and server NIS+ authentication.
server# nisauthconf dh640-0 des server# keylogin -r (screen notices not shown) server# /etc/reboot