Background: Differential abundance testing is an important aspect of microbiome data analysis, where each taxa is fitted with a statistical test or a regression model. However, many models do not provide a good fit to real microbiome data. This has been shown to result in high false discovery rates. Permutation tests are a good alternative, but a regression approach is desired for small data sets with many covariates, where stratification is not an option. Results: We present an extension of the Permutation of Regressor Residuals (PRR) test suitable for microbiome data, and a new R package ’llperm’ which implements popular regression models in this framework. Simulations based on real data show that the approach outperforms the likelihood based models in both Power and False Discovery Rate. The PRR-test approach is able to maintain the correct nominal false positive rate expected from the null hypothesis, while having equal or greater power to detect the true positives as models based on likelihood at a given false positive rate. Conclusions: The PRR-test was shown to provide a useful new tool for microbiome data analysis. Likelihood models can have a shockingly high rate of false positives and it is not possible to adjust for this in real data sets where the ground truth is unknown. As standard models may not provide a good fit to data, robustness gained from this approach can be viewed as a major benefit.