Kmeans using silhouette_score
Do some measurements to identify your bottlenecks.

Here, I suggest to not use Silhouette. Because it is much slower than k-means. Silhouette need O(n²) distance computations every run!

The obvious was to speed this up would this be to compute and store a distance matrix just once. This won't help k-means, but it will make multiple Silhouette runs a little bit faster (it will still be O(n²), but only array lookups instead of distance computations now). Nevertheless, this will not be scalable to large data.

The better approach is to use a cheaper heuristic to guess the "best" value of k. None such measure is perfect anyway.