You should redesign the primers in my opinion. Primer length actually isn't that important as long as it works. You are already running well below the usual annealing temperatures. But do not worry, all is not lost! I have a few suggestions.

I would sincerely recommend going farther outside the gene and looking for a site that will make primers with a high GC content. You can always amplify a larger portion beyond the gene and then after purifying the longer version, use it as template with these primers.

Additionally, you can troubleshoot and figure out which primer is failing you. Design primers somewhere inside the gene at a point with a high GC content. Basically creating shorter parts of the first part and last part of the gene. If one is able to make a PCR product and the other is not, then you will know which one is causing problems.

Usually PCR machines will allow you to run a gradient of annealing temperatures. Make up a bunch of samples and run a PCR with one sample at each temperature across the gradient. Then run them out on a gel and note which temperature gives you proper bands.

I think that your Tm's are far too high. In the future I would recommend this Oligoanalyzer for looking at potential primers. I've just checked yours and the Tm is as low as 47 degrees for the forward primer. It's also useful for looking for hairpins and self dimers. Then one should put both primers in for a check for heterodimers. http://eu.idtdna.com/analyzer/Applications/OligoAnalyzer/

As noted by New England Biolabs, increasing the amount of bases on either side of the restriction sites will increase cleavage efficiency. Perhaps something to consider for next time: http://www.embl.de/pepcore/pepcore_services/cloning/pcr_strategy/primer_design/

You should redesign the primers in my opinion. Primer length actually isn't that important as long as it works. You are already running well below the usual annealing temperatures. But do not worry, all is not lost! I have a few suggestions.

I would sincerely recommend going farther outside the gene and looking for a site that will make primers with a high GC content. You can always amplify a larger portion beyond the gene and then after purifying the longer version, use it as template with these primers.

Additionally, you can troubleshoot and figure out which primer is failing you. Design primers somewhere inside the gene at a point with a high GC content. Basically creating shorter parts of the first part and last part of the gene. If one is able to make a PCR product and the other is not, then you will know which one is causing problems.

Usually PCR machines will allow you to run a gradient of annealing temperatures. Make up a bunch of samples and run a PCR with one sample at each temperature across the gradient. Then run them out on a gel and note which temperature gives you proper bands.

I think that your Tm's are far too high. In the future I would recommend this Oligoanalyzer for looking at potential primers. I've just checked yours and the Tm is as low as 47 degrees for the forward primer. It's also useful for looking for hairpins and self dimers. Then one should put both primers in for a check for heterodimers. http://eu.idtdna.com/analyzer/Applications/OligoAnalyzer/

As noted by New England Biolabs, increasing the amount of bases on either side of the restriction sites will increase cleavage efficiency. Perhaps something to consider for next time: http://www.embl.de/pepcore/pepcore_services/cloning/pcr_strategy/primer_design/

Can you tell me the detailed your genomic PCR conditions (PCR reagents, Conc. of gDNA templete...) ?

Please share the detail PCR reaction, so we can able to discuss. Due to low GC content in primer, I will also recommend you to go for new primer design. Please follow the mitchell and anshul's suggestions.

you should see their 3' end, that's where the Taq polymerase starts adding nucleotides and that's where the design must be smart: you should be careful there is no primer dimer formation possibility and the deltaG is negative enough (around -13 to -15) [that's the drop in energy when it anneals to its target sequence]. In simpler terms it means you should have at least 3 GC pairings in the last 5 nucleotides of your primer for example GatCC, or ...GCtCC, etc). You might have noticed that the last two pairings are always GC AND you never use GC, only GG or CC, which reduces chances to get primer dimers.

and more thing is Processivity of the Taq polymerase is important when you work with longer amplicons. Taqs are nowdays all engineered for these three aspects: speed, proof-reading and processivity. Different Taqs are better in one or some of these aspects. I would suggest using the Phusion polymerase for your amplification.

4. You say you don't amplify your gene. Still, it would be good to know how your gel looks like, is it completely empty or do you see a smear or distinct unspecific bands? This refers to what I was saying at the beginning, it might be difficult in your conditions remove unspecificity since you cannot raise too much the annealing temperature. Although at 56, even 55, °C you can obtain specific amplification. in any case, sometimes primers have slow binding kinetics, don't be afraid to anneal for 1 min or 1 min 15 sec, it will never harm. Secondly, you can elongate longer time, proof reading Taqs are slower, it's part of the proof reading process, so you can amplify for up to 4 min without problem (considering an amplification speed of 500 bp per min). Lastly, you might want to design external primers to the CDS you need (which constraints you on the primer design) in the 5' and 3' UTR of your gene (if they are known, but few extra bases can be sufficient), which are more specific, following the rules I was describing in point 2). Keep in mind that a good primer will have Tm 58-62 °C with a length of 18-20 nt (which means a GC content above 50%). You can run a second amplification on a dilution 1/10-1/50 of your first amplicon with your present primers. I hope it will help you...