There is a dilemma, but I don't think it's loss of legitimacy so much as authority. They are quite similar but not the same; an institution that loses authority but is still legitimate, and there is potential for it to regain authority (like the strategic concept of a "fleet in being").

But for many states, they have significantly greater power by virtue of being in the EU than they would without. Arguably, even the UK lost power by leaving.