Where is Time Machine restoration software installed?
The Time Machine backup can be restored once the  operating system has been reinstalled.

I would create a bootable usb flash drive with the macOS of your choice on it. There are other ways of prepping the drive but I like Diskmaker X. It's free/shareware and the developer has versions available for pretty much every (recent) version of macOS. There are other utilities and there is even a command line option depending on what version you want to install.

Once you have installed your new SSD and installed the OS of your choice you need to restore your apps and data. there are lots of tutorials out there on how to do this but it boils down to a few simple steps. Be sure and have your Time Machine backup drive connected when you do this.


Hold down the ⌘ Commandand R keys to start up in Recovery mode
Select Restore from Time Machine Backup and click Continue.
Select Restore Your System, click Continue and select your backup.


The restore process will take a good long while and the Mac should restart or prompt you to restart when it is done.

While that is an overview and some of the details on the Recovery Mode option from restoring from a Time Machine backup are "best of my recollection" that should do it.