first of all, thank you for activating the support subscription!
The latest version of EFSEO is fully compatible with Joomla! 3.6.5. How do you create the entries? You have to use the same URL scheme that you've selected in the plugin. So, if you use relative, non-SEF URLs than you have to enter the URL in this format.
Honestly, this is not the way how EFSEO should be used. You should enter the data directly in the frontend with the help of the modal window. But if you still want to use the backend to modify the data, then you should first collect the URLs (Option "Collect URLs" in the settings of the plugin) and then just update the entries in the component which will be generated automatically by the plugin with the correct URLs.
Please try it this way or post more information (see §2 in forum rules) so that I can help you!