Advances in microelectronics and the evolution of IoHT devices allow the collection and, consequently, generation of a greater volume of health data, intensifying the need for robust data privacy solutions. Traditional k-anonymity-based anonymization techniques often suffer from high information loss, especially as the anonymity parameter k increases. To address these challenges, this article proposes Generalization First k-Member Clustering (GFKMC), a novel k-anonymity method that applies early generalization to quasi-identifiers, reducing computational overhead and minimizing information loss. Unlike traditional methods (e.g., Mondrian, Top-Down Greedy (TDG), and Clustering-Based (CB)), GFKMC maintains nearly constant information loss (≈ 25%) across varying k values and better preserves machine learning model performance, especially in low k scenarios. Empirical evaluations demonstrate that GFKMC outperforms baseline methods by significantly minimizing the trade-off between data utility and privacy. Moreover, GFKMC preserves the performance of machine learning models more effectively.