No one questions why these physically perfect specimens walk around the lands, seemingly out of place. It is painful to do so. That is not a metaphor, thinking too much about where these beings come from and why no one seems to consider them out of place can kill you. Blood will drain from your eyes and ears in a steadily increasing torrent.
Barbarians are beings of pure chaos who appear to be physically perfect specimens that hail from some region beyond the horizon you can't place on any map. Think about that, but not for too long. Who does that remind you of? Elves. Barbarians are actually a type of elf.
They come from "Barbaria", a land of icy glaciers, or perhaps a steamy jungle, or perhaps even an ash littered volcanic hellscape. It always changes, and no one can think too long upon it. They are from the other world, like all faerie kind.
Their magic hides their origins, it grants them supernatural strength when they need it most. But like all faerie kind they have a weakness. Their magic is diminished by covering their skin. It is their appearance and pride that fuels their magics.
But you may think to yourself (which you should stop doing), Barbarians hate wizards! Oh this is true. Like all elves, their innate spells can be discerned by the prying eyes of sages and wizards willing to dissect their corpses (or vivisect their living bodies). As a matter of protection, barbarians must be aggressive in rooting out the prying eyes of wizards. To tell you they hate magic is only to keep their secrets safe.
Do not question where barbarians come from. Do not think on why no one sees through their glamour or how they perform such feats of strength. But keep your cold iron handy...