Clear[RandomLatinSquare]
RandomLatinSquare[n_] := Module[{out, ord},
  out = Table[RotateLeft[Range[n], i], {i, n}];
  out = RandomSample[out];
  ord = RandomSample[Range[n]];
  out = out[[All, ord]];
  out
  ]
RandomLatinSquare[5] // Grid