In this paper, we propose an efficient alternative to the affine-invariant Riemannian k-means algorithm on symmetric positive definite matrices. Recently introduced log-extrinsic means are coupled with the Jensen-Bregman log-det divergence, as a replacement for the Riemannian Fréchet mean and the Riemannian distance. Performances and computation times are compared for several frameworks on point clouds sampled from Riemannian Gaussians. Results show that our algorithm matches the clustering accuracy of the affine-invariant Riemannian k-means, while achieving runtimes comparable to those of log-Euclidean k-means.