My first attempts [...] gave me auc 0.85 on test set and 0.96 on training set. So, the model overfits.
This is not quite true.
See, (almost) each estimator will have a better prediction score on the training data than on the testing data. It doesn't mean each estimator overfit.
It is normal though to habe a better score on the training set, as the estimator is built on it, meaning its parameters are fitted thanks to it. However, your estimator can fit your training data more or less.
Let's take your Random-Forest example. If the depth is too high, you'll fit way to much to the training data : overfit. If the depth is not high enough, it will be hard to generalize to other data : you underfit.
- Underfitting :
0.96
on train set & 0.82
on test set
- Possible good fitting :
0.96
on train set & 0.89
on test set
- Overfitting :
0.96
on train set & 0.75
on test set
As a good data-scientist, you want your model to fit the data enough to generalize well but not too much not to overfit. To control how your model generalize, one uses cross-validation techniques. The value you get is pretty-much what you will obtain with new value ± the variance associated to this crossvalidation
PS: Using cross-validation too often on test data makes you, in a way, learning this data as you choose them to maximize your test score. It can lead to a form of overfitting for future new data.