Floating point imprecision at a mere ~5km from origin

I have a world that is 18000x14000. Navmesh "patches" are generated as needed, when needed, if needed, and water tiles disappear from far away. It runs fine even on my crappy laptop, but if the camera is at, for example, 3945 X and -2190 Z, I get severe vertex imprecision, despite the fact that the coordinates are nowhere near the amount usually found in cases of floating point imprecision.

Interestingly, also, is that the skybox shader breaks in these coordinates as well.. but only in the build. It's a custom shader by someone else. But that's a problem for another day, and can be fixed by the solution to the problem at large. The lighting, UI, terrain, basically everything flickers and distorts.

Here's a video demonstrating the issue as a whole.

Why do I need a world this big? Same reason as the Arma and Operation Flashpoint games. The game simply doesn't function the same way without a large world. However, I would expect vertex precision for both UI and lighting etc. to last a lot further than just ~5km from origin. I am using Unity 2019.3.15f1, the latest stable build that I know of.

What can I do without moving the map every time the player wanders too far from the origin, and without breaking seamlessness of the world traversal? Is it possible to reposition the origin, like it is in Unreal?