A quick look on Digikey showed me a few MOSFETs at about USD 3 a piece that can handle your current with on resistance of about 4 mΩ, which means they dissipate "only" about 10W at a 34A current. There are MOSFETs with an even lower on resistance, but the price goes up of course. You'd need a few other cheap components such as resistors and optocouplers, plus maybe a gate driver, though you're not doing PWM so probably not necessary. I guess you'd end up with about USD 100-150 total in new parts.
DC switching SSRs are usually also based on MOSFETs, so have the same heat problem and also need a heat sink. This heat is probably going to be your biggest challenge (the advantage of your relays is that they do not produce heat).
The rest of the project is relatively easy. You already know how to read your thermocouples, just have to connect all to a single Arduino (straightforward assuming you have enough analog inputs).
Another approach would be to keep the current rats nest, and have the things communicate. If the devices are reasonably close together you could connect them using I2C to a single master. That master would then regularly (ever second or so) query all the controller Arduinos for the temperature of the various probes; then based on that tell the slaves which heaters to switch on and which to switch off.