R, 68 75 bytes

function(n,m=combn(1:n^2,n),p=sample(rep(which(colSums(m)==n^2),2),1))m[,p]

Try it online!

Take that, sample!

R, 68, 75 48 bytes (random) and 70 bytes (deterministic)

@Giuseppe's rejection sampling method:

function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}

Try it online!

Golfed original:

function(n,m=combn(1:n^2,n))m[,sample(which(colSums(m)==n^2)*!!1:2,1)]

Try it online!

The *!!1:2 business is to avoid the odd way sample act when the first argument has length 1.

R, 68 bytes

function(n,m=combn(1:n^2,n),p=sample(which(colSums(m)==n^2),1))m[,p]

Try it online!

R, 68 75 bytes

function(n,m=combn(1:n^2,n),p=sample(rep(which(colSums(m)==n^2),2),1))m[,p]

Try it online!

Take that, sample!