I think sometimes you just have to go with it... crazy stuff can happen with gendered words. It's the same in Spanish: las llaves.
Are you asking why it's not automatically masculine? The masc. ending is -o, although that's not the be-all, end-all rule. Again, crazy stuff.
Yeah. It's all to do with how the words came from Latin. Some changed gender over time (folium = leaf to Spanish hoja, for instance: masculine to feminine, because the plural is folia and it came from that), though most are the gender they are because they were that gender in Latin. It's history.
Exactly what I was about to reply... It's maybe because it comes from Latin "clavis", "claves", that is a feminine? Sometimes words keep their gender from Latin to Spanish or Portuguese, sometimes they are "fixed" by usage, I mean that a word with an ending that seems "illogical" to people who talk the language can turn into the opposite gender, it has simply not been the case with "Chave" in the Portuguese history of the language.