I suggest you read up on how TCP/IP, proxies and tunneling, and networking in general works. Your proxy is only as good as the proxy provider logging policy, what information the proxy transports from your end to the real end and its capacity. Your MAC is only important if you are not on your own network/behind Router/NAT.
If you want tips. Stop using public or for-rent proxies/VPN's and set up your own, that way making sure there are absolutely no logs on the tunneling server. Additionally, depending on what you want to do with your fresh proxy. Get another one and another one and [insert needed privacy level here * another one] and link them up.
EDIT:
There are many reasons to change your MAC address. If you are on an unfamiliar/public network OR someone else gets access to your network, your MAC can reveal your identity.
I've heard of USB adapters that could change the MAC address, as well as changing the IP of my router from my local ISP. Thoughts, sage?