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.