Failure credibility is popular in measuring safety degree of structure under fuzzy uncertainty, but the heavy computational cost is still a challenge in estimating the failure credibility. To alleviate this issue, an iterative method combining adaptive Kriging and fuzzy simulation (AK-FS) has been developed by Ling et al. However, for the problem with complex performance function, a large candidate sampling pool is needed in the AK-FS, which makes the training process of the Kriging model fairly time consuming. In order to improve the estimation efficiency of failure credibility through reducing the size of candidate sampling pool in AK-FS, an efficient sample reduction strategy based on adaptive Kriging (SR-AK) is proposed in this paper. In the SR-AK, the estimation of failure credibility is transformed into searching two active points in candidate sampling pool. After updating the Kriging model in each circle, current active points can be easily identified. Then, according to the properties of the active points and the prediction characteristics of Kriging model, the samples in current candidate sampling pool can be divided into two sets, i.e., the samples affect the estimation of active points and the samples have no effect on it. Obviously, the samples in the latter set can be deleted from current candidate sampling pool to reduce its size. By using this sample reduction strategy, the process for training Kriging model is accelerated circle by circle, which is very helpful to save the analysis time and improve the computational efficiency in estimating failure credibility. Four examples are employed to demonstrate the performance of the proposed SR-AK in fuzzy safety degree analysis.