The Global Health Security Index (GHSI) categorizes countries according to a composite score. It is proposed as a means to alert governments and health institutions about the gaps of national health systems to compromise with the detection and management of biological threats. Recently, several criticisms have been addressed to the scoring, ranking and segmentation process underlying the computation and usage of this index, the construction process and to the quality of information sources from which component indicators and sub-indicators are collected. In this article, we propose a multi-criteria ordered clustering procedure, based on the PROMETHEE II method and an iterative algorithm aimed to improve the segmentation of nations in the GHSI database. For robustness analysis purposes, this procedure is wrapped into an approach which considers the uncertain nature of data and parameters. The application considering 195 countries in the 2019's GHSI is performed. This approach is also compared to k-means. Clusters different from segments proposed in GHSI and k-means are found. Based on our robustness analysis, three groups can be identified: robustly assigned nations (clearly belonging to a cluster); weakly and possibly assigned nations (belonging to a cluster, but ambiguously); and non-assigned countries (without any cluster to allocate them). Results suggest that the 2019's GHSI segments should be reviewed.