Online and real-time estimation of the State of Charge (SoC) of batteries is an issue that affects several applications where energy storage systems are used. Among the most effective techniques for estimating the SoC, we find those based on Electrochemical Impedance Spectroscopy (EIS). One of the problems that afflict the EIS is that a single frequency sweep can last too long compared to the need to carry out the evaluation of the SoC online and real-time. This work aims to minimize the time required to perform EIS through a feature selection technique based on Genetic Algorithms. Specifically, an experimental campaign was conducted on 5 different Lithium Iron Phosphate batteries to create a dataset, and a feature selection evaluation strategy was implemented. The obtained results confirmed that it is possible to reduce the time required to perform EIS while maintaining good performance in SoC estimation.