They didn’t prove non-locality - it was disproven that you could have a local hidden-variable theory. This doesn’t mean any valid theory has to be non-local.

Tl;dr: There are local theories, such as theories based in the Many-Worlds Interpretation, that are able to explain these results by basically saying “It is not a definite outcome produced by some experiment that travels through space at the speed of light, it is the set of all possibilities, constrained by a logical relationship which determines what you can see or not, depending on what you’ve already seen”.

Local quantum theories are still on the table, perhaps most notably Everettian theories, which preserve locality by saying that the reason measurement results always agree – no matter when or how far apart they are performed – is due to decoherence.

I’m gonna try to represent the basic idea for anyone interested, but I first need to add that, while the Everettian take is contentious, it is the only explanation that doesn’t introduce any extra assumptions. It is the simplest possible explanation based on what we know – no extra conjecture required – and it is basically the idea that “hey, we have the Shrödinger equation - the one that’s at the core of all quantum mechanics; we think that is how reality works and not just an incomplete description of it”. Other interpretations require extra laws of physics (so far without any convincing experimental support) to explain reality.

When you measure some property of a system (one or more “particles” inside some bounded region of spacetime), you are entangling yourself with that system. By entangling yourself with a system in superposition, you are put into superposition as well. Being in superposition means that there are many possible versions of you (all the possible solutions to the question “what facts make sense together”), but none of ‘you’ can really say for sure that any other ‘you’ exist, because you’re not compatible with each other anymore. They don’t make sense combined and the universe can’t exist in such a state.

Let’s look at how this plays out in an experiment. Let’s say you have a “particle”, A, that exists in a superposition between “spin-up” and “spin-down”. It is entangled with another similarly superpositioned “particle”, B, such that if A is spin-up, B is spin-down and vice versa. Now, B happens to be very far away, and so is your colleague who is about to perform the same measurement as you but on B. They are so far away that there is no way for A and B to “shake hands” across this distance before both measurements have already been performed, so they can’t “come to an agreement” on whether they “ought to become” spin-up or spin-down.

You and your colleague now perform their measurement and go into superposition; you both observe spin-up and spin-down but in separate “realities”, “branching the universe” into mutually exclusive possible worlds. When “local causality” (which propagates through space at the speed of light) eventually reaches you and tells you what the “outcome” of the measurement on B was, you had already learned what your measurement showed, and woah… they agree! One was indeed spin-up and one was spin-down! Both versions of you would agree on that fact if they/you could talk to each other/yourself, but not on who observed which result. Unfortunately/fortunately, you can’t talk to the other you, so as far as each of you know, the result was ‘randomly’ either spin-up or spin-down - certainly not both!

The key insight to make sense of the above is that the measurement results still had to travel through space at the speed of light (via a long chain of entanglements/“particle interactions”) - there was never any violation of locality; no faster-than-light communication. Both possibilities reached you at the same time, but only a total of two possibilities were ‘coherent’ - not four; (A=spin-up ⋀ B=spin-down) ⋁ (A=spin-down ⋀ B=spin-up).

How did they know which states were compatible? Well, the fact that A and B were entangled (i.e. their states were bound by some relationship - in this case, the logical relationship stated above) suggests that they “shook hands” at some point in “the past”, and by the principle of locality that means they “physically interacted”, either directly or indirectly, and the logical relationship between their states was established as the only possibility back then.