I would create a new ID Field and keep the old ID's.
Then you can use "Replace Field Contents" once, not in a loop. To fill the new ID field for all records with a serial number.
Then you need to create a relationship between the table and the related table based on the Old ID so they are still correctly related.
In the related table you also make a new field for the new Foreign ID.
Then you use a Replace Field Contents step again (not a loop) to fill in the new ID from the main table.
When you are certain that the new ID's have been filled in correctly you can change the relationship to base it on the New ID fields.
Thank you Guy, I'll give this a try, I appreciate the help.