Yes, GDPR changes the frame of reference to call recording considerably. There are fundamentally 6 key things you need to think about;
1 - The people involved in the call have given consent to be recorded
2 - The recording is necessary for the fulfilment of a contract
3 - The recording is necessary for fulfilling a legal (regulatory?) requirement
4 - The recording is necessary to protect the interests of one of more participants
5 - The recording is in the public interest, or the exercise of official authority
6 - The recording is in the legitimate interests of the recorder, unless those interests are overridden by the interests of the participants in the call
So, 1 - means that you have to have required consent and have been provided it no matter what. We know that already.
2, could be used by BPO type organisations (potentially, as their contract requires it). It would make for an interesting IVR prompt for sure
3, Easy if you are a Bank, Insurer or other such regulated industry sector
4, Might be useful to you if you are not in a heavily regulated industry
5, Useful if you are in the public sector, emergency services, government etc
6, Could be used by any organisation that can reasonably argue it is both in their and the callers interest for the substance of the call to be recorded
So, you have a few choices. In any case you will need to give really good thought to your new IVR or greetings systems so that your 'tone' reflects these changes and encourages opt in. Also, capture updated stats and metrics so you can improve the experience and efficiency over time.
The best practice I think is not to hide behind GDPR and blame it. Embrace the change and own it from your organisational perspective and give your 'clients' the opportunity to understand there is an upside for them in this too, for example, proof of promises made by either party etc
You could fundamentally still argue that the recording is necessary for 'training purposes' but you still need to get CONSENT (1) and then use (6) for your justification. Assumed consent is not sufficient; it must be an opt-in with explicit consent; so even if you continue to use 'training' as your leverage you will have a changed front-end experience to gather the consent in any case. You are likely to be using an assumed consent having played the standard industry wide 'training' message to date without asking for caller input or confirmation.
Best of luck!