Generate random matrix and its inverse
Efficient Generation of Random Nonsingular Matrices by Dana Randall covers exactly this topic. In particular Corollary 1.1 states:


  We can uniformly generate a matrix and its inverse in time $2M(n) + \mathbb{E}[O(n^2)]$.


Where $M(n)$ is the time it takes to multiply two $n \times n$ matrices.

Unfortunately this is not better than what you had hoped for.