A partial answer for the case that the sets $\{a_1,\dots,a_k\}$ and $\{b_1,\dots,b_k\}$ are linearly independent (or equivalently, the Grammian matrices are invertible).
Suppose that $G(a_1,\dots,a_k) = G(b_1,\dots,b_k)$. Let $\{a_{k+1},\dots,a_n\}$ and $\{b_{k+1},\dots,b_n\}$ be orthonormal bases for $\{a_1,\dots,a_k\}^\perp$ and $\{b_1,\dots,b_k\}^\perp$. Verify that $G(a_1,\dots,a_n) = G(b_1,\dots,b_n)$.
Note that a linear map $f:V \to V$ is orthogonal if and only if $(f(x),f(y)) = (x,y)$ for all $x,y \in V$. Show that if we take $f$ to be the unique linear map satisfying $f(a_j) = b_j$ for $j=1,\dots,n$, then $f$ satisfies this property and is therefore orthogonal.
An extension of this solution to the general case:
Because $A^TA = B^TB$, we have $\ker A = \ker B$. It follows that a set of vectors $a_{j_1},\dots,a_{j_d}$ will be linearly indepnendent if and only if the corresponding set $b_{j_1},\dots,b_{j_d}$ is linearly independent.
With that in mind, we can select a set $a_{j_1},\dots,a_{j_d}$ that forms a basis of $\operatorname{span}(\{a_1,\dots,a_k\})$ (which has dimension $d$). The corresponding set $b_{j_1},\dots,b_{j_d}$ forms a basis for $\operatorname{span}(\{b_1,\dots,b_k\})$. As before, we select vectors $a_{d+1},\dots,a_{n}$ and $b_{d+1},\dots,b_n$ that form bases for the respective orthogonal complements of the spans.
Now, it suffices to define $f$ to be the linear map satisfying $f(a_{j_\ell}) = b_{j_\ell}$ for $\ell = 1,\dots,d$ and $f(a_\ell) = b_\ell$ for $\ell = d+1,\dots,n$.
Best Answer
Yes, this is always true. Note that swapping columns $i$ and $j$ is equivalent to multiplying on the right side by the elementary matrix $T_{ij}$ which is defined by swapping rows $i$ and $j$ of the identity matrix. You can check that this matrix is the inverse of itself. Also, multiplying by $T_{ij}$ on the left side is equivalent to swapping rows $i$ and $j$.
So if we call your matrix $A$ then $AT_{ij}$ is the matrix that you get that swapping columns $i$ and $j$. Then its inverse is $T_{ij}A^{-1}$ which is the matrix that you get when you swap rows $i$ and $j$ in $A^{-1}$.