We claim that Alice requires a minimum of $n-\gcd(n,k)$ moves. Consider a graph over vertices labelled $1$ to $n$. If the card at position $i$ has number $j$, we draw a directed edge from $i$ to $j$. Since each vertex has indegree 1 and outdegree 1, the graph is composed of disjoint cycles. We consider what happens when we swap two cards. If they were from different cycles, the two cycles will combine after the swap. On the other hand, if they were from the same cycle, the cycle would split into two. In either case, the number of cycles increases by at most 1. At the start, there were $\gcd(n,k)$ cycles, while at the end there should be $n$, hence at least $n-\gcd(n,k)$ moves are needed. We show that Alice can achieve her goal in $n-\gcd(n,k)$ moves. Colour all cards with numbers $1,2,\cdots, \gcd(n,k)$ with blue and the rest red. Note that in each cycle, exactly one of the cards is red. For each cycle, continuously swap the red card with the card it points to. This will remove one blue vertex each time, needing $\frac{n}{\gcd(n,k)}-1$ moves per cycle to completely sort it. Hence $n-\gcd(n,k)$ moves is sufficient.