Here is the idea of the proof that the number of vertices in such a graph is at least $n^2$.   See step 7 for the hole in the proof. <strike>I believe it can be patched.</strike>  
**Edit:** As was shown in comments there are a lot of problems with this attempt. I am in doubt whether it can be patched or not.

Step 1: Cut the graph at any shortest loop (its length $l\geq n$). You will get a graph on a cylinder (imagine it as a "vertical" cylinder) with a correspondence between edges and vertices on its bottom to edges and vertices at its top. Lets call these bottom edges as $e_1,\dots,e_l$ and top --- $e'_1,\dots,e'_l$.   

Step 2: Take any shortest dual path between correspondent edges on the top and on the bottom of the cylinder. It corresponds to a noncontractible dual loop on the torus and its length $k\geq n$. Cut the cylinder at the vertices "just to the right of this path". Now we have a graph on the square with correspondence between vertices on its left to vertices on its right. Denote "left" vertices by $x_0,\dots, x_m$ and right by $x'_0,\dots, x'_m$, sorted from the bottom: $x_0$ and $x'_0$ are vertices at the bottom correspondent to $x_m$ and $x'_m$.  

Step 3: Start $n$ dual paths $p_1,\dots,p_n$ at edges $e_1,\dots,e_n$. Assume $x=x_0$ are current left vertex and $x'=x'_0$ --- current right vertex.  

Step 4: Suppose on this step $x=x_i$ is the current left vertex and $x'=x'_ j$ --- current right vertex. "Move up one of these vertices": if $i< j$ let $\widetilde x=x_{i+1}$ to be next current left vertex and if $j< i$ let $\widetilde x'=x'_ {j+1}$ to be the next current right vertex. In the case $i=j$ draw the shortest path from $x_{i+1}$ to $x'_ {i}$ and the shortest path from $x_{i}$ to $x'_ {i+1}$. At least one of them has length at least $n$. Choose it and let $\widetilde x= x_{i+1}$ or $\widetilde x'=x'_{i+1}$ correspondingly to the choice.  

Step 5: Assume, that we have just defined $\widetilde x$ on step 4 (otherwise we have defined $\widetilde x'$ and this step should be rewritten correspondingly). Prolong $p_1,\dots,p_n$ to the shortest path from $\widetilde x$ to $x'$ avoiding intersections (all edges of $p_1,\dots,p_n$ should be different). To show it is possible define $d(v)$ to be a distance from vertex $v$ to $x'$ (length of the shortest path). Suppose last edge of $p_j$ joins vertices $v$ and $w$. Then $|d(v)-d(w)|=1$, since this edge is the part from the shortest path from $x$ to $x'$. Let $d_j=\min(d(v),d(w))$. On this step add to $p_j$ only edges connecting vertices of the same type (i.e. $|d(v)-d(w)|=1$ and $\min(d(v),d(w))=d_j$). Use only vertices between two shortest paths: between $\widetilde x$ and $x$ with $x'$. Note that all $d_j$ are different. This proves that $p_j$ will not intersect with others. Finally set $x=\widetilde x$.  

Step 6: If $x\neq x_m$ or $x'\neq x'_m$ go to step 4. Otherwise go to step 7.  

Step 7: Note that now we have $n$ dual paths $p_1,\dots,p_n$ from the bottom to the top of the square. All we need is to assure that they correspond to the cycles of the initial graph (because in this case each of these cycles has length of at least $n$). To achieve this, I believe, we should do step 5 more accurately.