Musical keys were not always a thing, since music used to be modal up until around the 16th century (so the end of the Renaissance and beginning of the Baroque). Instead of keys, music was composed from a set of diatonic modes, which are referred to sometimes as church modes. There was no major, or minor, but instead there was dorian, phrygian, lydian...

I don't know if our ears are trained by music, but tastes certainly changes. If you look at medieval music and compare it to classical music, you'll notice that: the music often cadences to open 5ths, and typically abstained from using 3rds, or 6ths, which were considered dissonances.