I can think of several reasons why the federal government can and should own land in a state; leaving aside how the feds need some land to operate things like military bases, courts, and administration buildings, there's the fact that the states collectively and knowingly ceded ownership rights over certain land to the federal government when they, the states, created the Constitution (see the Property Clause).
Every bit of land outside the first thirteen legally began with federal ownership: The original thirteen states surrendered all their claims to the land west of the Appalachians when the Constitution was ratified, the Louisiana Territory was purchased by the federal government with federal funds, the Southwest was given to the federal government as part of the treaty that ended the Mexican-American War, and the Oregon Territory was ceded to the federal government by the Treaty of 1818, Alaska was bought by the feds from the Russians, and Florida was given to the feds by treaty with the Spanish. I won't profess to know how federal land in the original thirteen states was acquired (I assume largely by purchase), but the legal right and history of federal ownership of state lands is pretty cut and dry (Hawaii admittedly being something of an odd duck), and has existed since the days of the Founding Fathers. If anything, thirty-seven of the states were wholly owned by the federal government before the feds ceded some of that land to the locals.*
You're free to argue the policy wisdom of retaining federal ownership of land vs. ceding all of it to the states, of course, but legally the issue has been settled for quite some time now. Don't forget that the federal government is entirely a contractually-created creature of the states; if they felt that the feds should give up all of its land, they could have made it that way. For that matter, they still can. Instead, they consciously surrendered some of their own land (not a small concession, if you know how rancorous those fights were in the colonial days), and have not made any real concerted effort to change the situation since then.
In the meantime, regarding Nevada specifically, the reason it's federal ownership rate is so high is simply because no one wanted to buy land there when it was first offered: I don't know if you've ever been, but there's a reason 95% or so of the population lives in only two counties, and if hadn't been for a silver boom (and later legalized gambling) I'd wager Nevada would never have reached the population rate it takes to become a state: the place is largely uninhabitable.
*We are ignoring the whole issue of people who lived on said lands before the territories were ceded to the feds, most notably the Native Americans but also French, Mexican, British, Russian, and even American settlers, only some of whom were covered by the treaties encompassing their territory and only some of whom previously answered to the sovereign who handed the land to the federal government.
I mean, I get how the situation came to be. And I certainly understand that the federal government has thoroughly validated the federal government's ability to own and administer property for a very, very long time now, to the point that it's pretty much all settled law by now. So I don't argue that it's a violation of sovereignty in the legal sense, but rather in the practical sense. While things may nominally be the same as they've ever been, the situation between the states and the feds has changed quite a lot in practical terms as technology and the bureaucracy have advanced. The total state wasn't a possibility until now. Where the federal government in the 1800s would have little interest in micromanaging backwaters like Nevada, and even less ability to do so, today it's a relatively simple thing.
Clearly the desire is there, too. People have long made their careers in government by expanding their agency, thus making it more important. There seems to be a common thread of mission perversion running through a lot of the stories involving federal agencies in recent years: the ATF engaging in weapons trafficking, the DEA climbing into bed with the Sinaloa cartel, and the continuing politicization of the IRS. Here we have seen an effect of the BML's efforts to drive ranchers away during the salad days of the housing bubble. In absence of some serious blowback, it's a trend we can probably expect to continue.
You are ostensibly correct that states which object to the current state of affairs "merely" have to legislate it away, but that is akin to saying that if I didn't like Obama I could "merely" have elected someone else.