Since you are a veteran (you mention your VA checks) you should check out USAA.
https://www.usaa.com/ It is a bank/credit union for military personnel, and they are WONDERFUL. Best customer service, ever! Your check can be direct deposited and the auto payment done each month, just like now. You can use any ATM (they will refund the charges up to 5/month) to make cash withdrawals. Free transfers and bill pay. No fee debit card. In fact, no fees at all. You need to keep $25.00 in a savings account. They have the cheapest car insurance we have ever found. They also have the best rates on car loans, mortgages, etc. Your only problem would be depositing cash. I don't think you can do that, but call them up. You may be able to. Good luck!