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.
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}$.