If you want an explicit construction (that does not involve randomness), you can use classical constructions of Ramanujan graphs, such that the one from [this paper of Morgenstern][1].

Given an odd prime power $q$ and an even integer $d$, Theorem 4.13 in that paper gives you a Cayley graph on $n\sim q^{3d}/2$ vertices, with degree $q+1$, and girth $g$ at least (roughly) $2d$. So the number of edges is (roughly) $n^{1+3/2g}$.


  [1]: https://doi.org/10.1006/jctb.1994.1054