While linear mixed-effects (LME) models are common for analyzing longitudinal data, most users rely on random intercepts or simple stationary covariance, due to unavailability of computationally tractable solutions. Here, we extend the Fast and Efficient Mixed-Effects Algorithm (FEMA) and present FEMA-Long, a computationally tractable approach to flexibly modeling longitudinal covariance suitable for high-dimensional data. FEMA-Long can: i) model unstructured covariance, ii) model covariates as smooth functions using splines, iii) discover time-dependent effects of covariates with spline interactions, and iv) use these flexible longitudinal modeling strategies to perform longitudinal genome-wide association studies and discover time-dependent genetic effects, in a computationally scalable manner, suitable for high-dimensional data. Through extensive simulations, we show that estimates from FEMA-Long are accurate, while being up to several thousand times faster and with minimal carbon footprint. To show the utility of FEMA-Long for discovering novel biological signal, using data from the Norwegian Mother, Father and Child Cohort Study (MoBa), we performed a longitudinal genome-wide association study with non-linear SNP-by-time interaction on length, weight, and BMI of 68,273 infants with up to six measurements in the first year of life. We found dynamic patterns of random effects including time-varying heritability and genetic correlations, as well as several genetic variants showing time-dependent effects, highlighting the applicability of FEMA-Long to enable novel discoveries.