An interface isn't a magic get out of jail free card that makes swapping out an implementation trivial. And if it is, it's because it was done so from painstaking effort, and probably maintaining at minimum two implementations.
Manual TDD (not using a mock framework) practically requires dependency injection and thus interfaces[1] and a minimum of two implementations for each: the real one that does the work, and the one or more with minimal functionality that are passed in to other components when they're doing their own unit tests. Sometimes it even makes sense to have more than one test implementation depending on the needs of the various components that need to test against that interface. And in my experience that does act as a forcing function for making swapping out an implementation trivial. Or, as I prefer to call it, properly separating concerns.
[1] Or I suppose one could use an abstract class, but I've found interfaces cleaner.
Drastic fixes and Rewrites almost always consist of three things:
1. Writing tests to ensure functionality
2. Writing an interface or shimming the existing functionality to redirect control flow
3. Implementing and testing the rewritten functionality/improvements
Obviously you can't do it everywhere, but life is much better when (2) was done up front.
One of the biggest dimensions that completely change this conversation is: module boundaries. If you're in a position to touch all of your user's code, it's night and day vs if you're pushing migrations on other teams or God forbid customers.
But if you have all of your code? In Java atleast, it's cake.
Releasing rewrites / redesigns behind a feature flag, with a couple of strategic if statements is usually good enough. Noone cares that you had to change code outside of your interface for a release or two.
(Finding abstractions to solve given expression problem ain't easy too, but ultimately it may be better effort for library authors)