Hmm… quite right: the word republic doesn't refer to the relationship of city states, but to the source of political power. But a republic doesn't necessarily require an elected leader, merely some form of governance by public consent, whether that's elected officials or a true democracy where lawmaking is done by popular caucus and vote. You haven't given much detail on the demographics of your city state. If the entire populace is made up of magic users, then it could certainly still be a republic. Otherwise, it's likely some sort of meritocracy, where political power is based on magical ability. That doesn't really help you name it, though!

In the real world, a concordat is usually an agreement with the Roman Catholic Church. I think that carries a sufficiently mystical connotation.