Congratulations, 13K on a medium map is at the very least a good, solid score!
Some key points to higher scores (taken from discussions of far better players than me - I can't remember submitting any scores higher than 13K):
1) Speed. Just take a look at the ZYW (zero-year-win) thread to see the impact. Scores up to 40K have been achieved on tiny maps, by completing a military victory as soon as Metaverse allows it (which is somewhere in April, finishing sooner trips a cheat flag)
2) Speed in getting each score component (social, tech, military, econ) up. Crucial buildings here are econ capital, tech capital, manufacturing capital, spin control center. And the mind control center before it was fixed
Conquering minors and AI home planets works wonders for this as soon as they built some of those capitals.
3) Advanced weapons to boost military score, especially if you choose to be evil.
4) Difficulty: higher levels than "normal" give a higher score multiplier. In addition being forced to keep up with stronger AI's will make you improve faster too.
5) Game settings such as galaxy size, tech rate, availability of planets/stars/anomalies/... The more habitable planets, the higher your population (society score), economy and therefore military you can support.