Are you supplying any retailers with their brand or are you own branded? Do you supply business to business? That's where I'd look first as to whether there is a specific customer desire for SQF or FSSC. But I agree with previous posters, you don't normally need both.
From experience (brief) with both SQF and FSSC is I prefer SQF or BRCGS as GFSI standards particularly in sites where there isn't all that much experience. FSSC from my limited experience allows a lot more leeway on interpretation. My thoughts are that something like SQF might give you a bit more structure to what is required especially while you build experience, so if I had the choice, I'd go for that.
Renumbering is (excuse my language) a ball ache. To start with I'd identify the documents you have and pull together a live document list if you don't have one. Number, what it is and what version number. If you don't know why that version was created (unless it was v1 so "new document") then you'll have to leave it blank or put something in about having inherited the system.
Then rather than renumbering, I'd probably combine gap analysis and audit into one in readiness for whatever GFSI you go for. So work your way through with your team and other auditors. Take the section of GFSI standard, take your procedures, see how compliant they are then go out and see if the reality matches both your procedure and the standard. If the FSQMS has been a bit neglected, you will probably find that most of those document need major or minor adjustments. If you like as you go you could create a new numbering system but the numbering is secondary to the content in my mind.
I would suggest though that you start with HACCP before all of the above. You sound like you've had a very major change in people so that should prompt a review anyway. At least once you've done that you can rest a little easier before getting all your FSQMS ducks in a row.