Is there an efficient way to cluster a graph according to Jaccard similarity?
Any hierarchical clustering algorithm should meet your needs.  There are many efficient methods for hierarchical clustering; you can use any of them for your application.

With agglomerative (bottom-up) clustering, you simply keep merging clusters until all clusters have at least $k$ nodes.

With top-down clustering, you keep splitting clusters, except that if the algorithm tells you to split some cluster in a way that would leave one of its subclusters with fewer than $k$ nodes, you cancel the split and mark that cluster as finalized.

In general, hierarchical clustering gives you a tree.  You can pick any consistent cut through the tree that leaves all clusters of size $\ge k$.  So, it is easy to adapt any hierarchical clustering algorithm to satisfy your requirement that all clusters have at least $k$ nodes.  Many of the hierarchical clustering methods let you use any pairwise distance function, so you can use them with your Jaccard similarity metric.