Network Manager 1.4.2 has been testing very well for me the last few days...
This new version appears to randomize MAC addresses properly, and the
feature set has evolved to the point where the randomization process is
managed in a more holistic way. For example, you can specify a
cloned-mac-address type of 'stable', and this will generate a random MAC
(for a given access point) and store it for use with the same AP in the
future. Setting it to 'random' will generate a random MAC each time it
connects, instead of remembering the address. You can also specify
bitmasks for randomization.
When disconnected, the MAC is changed regularly at a set interval.
Randomizing also works for ethernet, and is handled entirely by NM just
like it is now for wifi.
The network-manager 1.4.2 package is in Debian unstable repo and its not
hard to install in Debian stretch/9. I do recommend removing your old NM
connection profiles after upgrading, as randomization (while connected)
didn't work for me until I started with fresh connection settings
(created a new netvm). After installing, edit
/etc/NetworkManager/NetworkManager.conf in the template and add lines like:
[device-scan]
wifi.scan-rand-mac-address=yes
[connection]
wifi.cloned-mac-address=random
Then stop the template and restart the netvm.
More details here:
https://blogs.gnome.org/thaller/2016/08/26/mac-address-spoofing-in-networkmanager-1-4-0/
https://developer.gnome.org/NetworkManager/stable/NetworkManager.conf.html
man nm-settings
https://github.com/QubesOS/qubes-issues/issues/938
Chris