Ultimately, there are routers or modems involved, and they push some legacy protocols, and there's a lot of providers out there who offer modules for modern routing hardware that take those old protocols and push them quite transparently over modern data pipes. It's a reasonably well understood problem. It would not require reworking the whole thing, that's the whole point - you take what you have and push the data around using modern hardware that can ensure that the data is safe.
Even if all you have is a 7 bit-only "ASCII" link, you can still push HDLC/X.25 on top of it and then any other protocol you wish on top of that. All it takes is inserting new hardware at key points in the infrastructure. Eventually you can provision alternate links, in an emergency you can leverage public internet - it's better than downtime, and with proper cryptography it's actually more secure than legacy non-encrypted links.