In addition to the good answers I'd like to add something from my experience.
A rewrite is not always feasible for different reasons, for instance if you need to still add new features continuously. So if you need to take a step-by-step approach for recactoring you will have to accept that there will still be legacy code in place for a long time (or even forever depending on the lifetime of the software).
So most of the time you to make trade-offs where to invest your time when performing refactorings because a huge code base cannot be refactored at once.
In this case I would be pragmatic and start with refactoring in places where the highest benefits are expected. This could be, for instance, extremely buggy parts of the code or parts of the system where changes happen a lot.
If changes happen a lot refactoring of that part can provide great benefits as clean code can easier be changed than messy code.
Code that does not change often and is considered correct (i.e. does not have known bugs) should be touched at last on the refactoring journey. Or maybe it will never be touched at all...
I think most companies want to avoid unnecessary risks. As refactoring legacy code can be risky the risk should be taken for the right reasons and for code where it pays off.