I would add the new substrate, move everything over and use Dr Tim's along with Macrobactor7 to add additional bacteria to the tank. Monitor Ammonia and Nitrites. If either rises then you can use Seachem Prime/Safe at five times the dosage to neutralize the ammonia/Nitrites until biological back to speed. Prime/Safe only viable for 48 hours, therefore, keep administering until toxic levels settle. Test that are based on Free Ammonia will still show toxic levels but if you test for Ammonium then those should be below toxicity. I'm assuming other biological media hasn't been disturbed along with the rocks that may have acted as biological media.
As an alternative. Could setup the new tank with new substrate and use power-heads to circulate water while performing a fish-less cycle with just Dr Tim's. Once completed then move contents and add Microbacto7 to supplement heterotrophic bacteria. According to Tim Havonec, best to seed nitrifiers first and avoid the heterotrophic from competing for available substrate.
