Change stored remote host names in terminal application en mass
The host names are stored in the Terminal settings .plist  in the users /Library/Preferences folder:

~/Library/Preferences/com.apple.Terminal.plist




Edit the .plist

The easiest way to edit a batch of these is by editing the plist with a tool like VSCode (free) with the Binary Plist Extension or your favorite text editor with plist support.1  You can also convert the plist to XML (and back to binary) using plutil.2 This will allow you to use any text editor like TextEdit that doesn't natively support plist formats.

Important:  I suggest making a backup copy of the plist before you start editing in case you want to revert back to the original.

You can find all of your servers in the array under the PermanentServers key as shown below.  Simply go in and fix the FDQN as needed.  If the domain suffixes are all the same, a simple Find/Replace should speed through the task.



Save the file and reload Terminal.  For this example, I added the FQDN .newFQDN to each entry and restarted Terminal.  Here's the result:



Alternate Method using defaults read/write

You can get the names of the server with the defaults read command:

$ defaults read -app Terminal PermanentServers

(
    "host1.FQDN",
    "host2.FQDN",
    "host3.FQDN",
    "host4.FQDN"
)


You can set your new servers by overwriting that array with a new one as follows:

$ defaults write -app Terminal PermanentServers -array '(host1.newFQDN, host2.newFQDN, host3.newFQDN, host4.newFQDN)'


You can then reissue the defaults read command to check the results.  The upside to this is that you don't need TextWrangler and you can script it.  However, it's difficult to do a large number on the command line so, you'll want to edit it first in a text editor to make sure you have no mistakes.


1 In the first version of this answer, I originally referred to TextWrangler as it was a tool I originally used to view/edit plist files.  However, I've been transitioning to VSCode as it's cross platform - macOS, Windows, and even FreeBSD, I discovered a plist plugin that allowed me to finally get rid of TextWrangler, not that it's "bad" in any way; I'm just trying to streamline my dev tools.  

2 To convert a binary plist to XML for editing, issue the command plutil -convert xml1 foobar.plist.  Once you're finished editing, save it then convert it back to binary with the command plutil -convert binary1 foobar.plist