How to make a legacy system heavily reliant on Entity Framework more testable?

We have a fairly large system (~1m lines) which is heavily reliant on Entity Framework 6. This means our DbContext is passed around and used everywhere.

We also have lots of "unit" tests, that are using an actual SQL Server database. Each machine that runs tests has a dedicated database which gets wiped and set up with needed data before running each test.

This is of course not ideal in terms of speed, maintainability, ease of use, etc.

My end goal is to make all of our unit tests (~5k tests) not use an actual database, but a mock of some sort. I know this process is not going to be easy but I also want it to be as less painful as possible.

Guidelines and thoughts on the best way to approach this would be much appreciated.