We study covering codes of permutations with the ℓ∞-metric. We provide a general code construction, which combines short building-block codes into a single long code. We focus on cyclic transitive groups as building blocks, determining their exact covering radius, and showing a linear-time algorithm for finding a covering codeword. When used in the general construction, we show that the resulting covering code asymptotically out-performs the best known code while maintaining linear-time decoding. We also bound the covering radius of relabeled cyclic transitive groups under conjugation, showing that the covering radius is quite robust. While relabeling cannot reduce the covering radius by much, the downside is that we prove the covering radius cannot be increased by more than 1 when using relabeling.