This paper investigates the three-dimensional stability of a pair of co-rotating vertical vortices in a rotating strongly stratified fluid. In a companion paper (Otheguy, Chomaz & Billant 2006), we have shown that such a basic flow in a strongly stratified fluid is affected by a zigzag instability which bends the two vortices symmetrically. In the non-rotating flow, the most unstable wavelength of this instability scales as the buoyancy length and its growth rate scales as the external strain that each vortex induces on the other one. Here, we show that the zigzag instability remains active whatever the magnitude of the planetary rotation and is therefore connected to the tall-column instability in quasi-geostrophic fluids. Its growth rate is almost independent of the Rossby number. The most amplified wavelength follows the universal scaling $\lambda\,{=}\, 2 \pi F_h b \sqrt{{\gamma_1}/{\hbox{\it Ro}^2} +{\gamma_2}/{\hbox{\it Ro}} +\gamma_3 }$, where $b$ is the separation distance between the two vortices, ($\gamma_1$, $\gamma_2$, $\gamma_3$) are constants, $F_h$ is the horizontal Froude number and $\hbox{\it Ro}$ the Rossby number ($F_h=\Gamma / \pi a^2 N$, $\hbox{\it Ro}= \Gamma / \pi a^2 f$, where $\Gamma$ is the circulation of each vortex, $a$ the vortex radius, $N$ the Brunt–Väisälä frequency and $f$ the Coriolis parameter). When $\hbox{\it Ro}\,{=}\,\infty$, the scaling $\lambda \,{\propto}\, F_h b$ found in the companion paper Otheguy et al. (2006) is recovered. When $\hbox{\it Ro} \,{\rightarrow}\, 0$, $\lambda \,{\propto}\,b f/N$ in agreement with the quasi-geostrophic theory. In contrast to previous results, the wavelength is found to depend on the separation distance between the two vortices $b$, and not on the vortex radius $a$.